package com.wxweven.algorithm.array.bsearch;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author wxweven
 */
public class 有序数组小于等于某数的最后一个元素 {
    /*
     * 参考：https://transformerswsz.github.io/2021/03/12/%E4%BB%8E%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E6%9F%A5%E6%89%BE%E4%B8%8D%E5%B0%8F%E4%BA%8E%EF%BC%88%E4%B8%8D%E5%A4%A7%E4%BA%8E%EF%BC%89%E6%9F%90%E6%95%B0%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%EF%BC%88%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%EF%BC%89%E5%85%83%E7%B4%A0/
     * 举例 [2, 3, 5, 8, 9], 最后一个小于等于4的数是3
     * 举例 [2, 3, 5, 8, 9], 最后一个小于等于5的数是5
     */

    public int find(int[] arrs, int target) {
        if (arrs == null || arrs.length == 0) {
            return -1;
        }

        int res = -1;
        int left = 0;
        int right = arrs.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            if (arrs[mid] <= target) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return res;
    }

    public int find2(int[] arrs, int target) {
        if (arrs == null || arrs.length == 0) {
            return -1;
        }

        int res = -1;
        int left = 0;
        int right = arrs.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            if (arrs[mid] == target) {
                return mid;
            } else if (arrs[mid] < target) {
                res = mid;
                left = mid + 1;
            } else if (target < arrs[mid]) {
                right = mid - 1;
            }
        }

        return res;
    }

    @Test
    public void test() {
        int[] arrs = new int[]{2, 3, 4, 6, 8, 9};
        int index1 = find(arrs, 5);
        Assert.assertEquals(2, index1);

        int index2 = find(arrs, 8);
        Assert.assertEquals(4, index2);
    }

    @Test
    public void test2() {
        int[] arrs = new int[]{2, 3, 4, 6, 8, 9};
        int index1 = find2(arrs, 5);
        Assert.assertEquals(2, index1);

        int index2 = find2(arrs, 8);
        Assert.assertEquals(4, index2);
    }


}